package com.work.daily;

import java.util.*;

/**
 * title : 二叉树的中序遍历
 * solution : 非递归-迭代法
 * link : https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 * Created by suk on 2020/9/14.
 */
public class D12_InorderTraversal_94_02 {

    public static void main(String[] args) {

        D12_InorderTraversal_94_02 d = new D12_InorderTraversal_94_02();

        /**
         * [1,null,2,3]
         */
        TreeNode node = new TreeNode(1);
        node.left = null;
        node.right = new TreeNode(2);
        node.right.left = new TreeNode(3);

        /**
         * expect : [1,3,2]
         */
        System.out.println(d.inorderTraversal(node));
    }



    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        // 莫要忘判断stack不为空
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            // 移动到右孩子继续遍历
            root = root.right;
        }
        return res;
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
